package origami;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * Created by Tzachi on 06/11/2014.
 *
 * Another approach to the simple case from the phone interview
 * No need to add extra property (color) to node
 * but, uses more memory: guid instead of 2 bits of color
 *
 */
public class IterativeMethod implements ICycleRecognition{
    public Set<String> visiting = new HashSet<>();
    public Set<String> finished = new HashSet<>();
    public boolean findLoop(Node startNode) {
        if (startNode == null) {
            return false;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(startNode);
        while (!stack.isEmpty()){
            Node currentNode = stack.pop();
            visiting.add(currentNode.getGuid());
            boolean expanded = false;
            for (Node node : currentNode.getChildren()) {
                if (visiting.contains(node.getGuid())){
                    return true;
                }
                else if (!finished.contains(node.getGuid())) {
                    stack.push(node);
                    expanded = true;
                }
            }
            if (!expanded){
                visiting.remove(currentNode.getGuid());
                finished.add(currentNode.getGuid());
            }
        }
        return false;
    }
}
